package com.zghhost.codedemo.util;

import java.util.Arrays;

/**
 * @author guohua.zhang@zhaopin.com.cn
 * @Date 2019/6/10 10:05
 */
public class SortLianxi {
    public static void bubble(int[] is){
        for(int i=0,ic=is.length;i<ic;i++){
            for(int j=i+1,jc=is.length;j<jc;j++){
                if(is[j] < is[i]){
                    int tmp = is[j];
                    is[j] = is[i];
                    is[i] = tmp;
                }
            }
        }
    }

    public static void selection(int[] is){
        for(int i=0,ic=is.length;i<ic;i++){
            int min = i;
            for(int j=i+1,jc=is.length;j<jc;j++){
                if(is[j] < is[min]){
                    min = j;
                }
            }
            if(min != i){
                int tmp = is[min];
                is[min] = is[i];
                is[i] = tmp;
            }
        }
    }

    public static void insertion(int[] is){
        if(is.length<=1){
            return;
        }
        for(int i=1,ic=is.length;i<ic;i++){
            int current = is[i];
            int j=i-1;
            for(;j>=0 && current < is[j];j--){
                is[j+1] = is[j];
            }
            is[j+1] = current;
        }
    }

    public static int[] mergeSort(int[] is){
        if(is.length<=1){
            return is;
        }
        int mid = is.length / 2;
        int[] left = Arrays.copyOfRange(is,0,mid);
        int[] right = Arrays.copyOfRange(is,mid,is.length);
        return merge(mergeSort(left),mergeSort(right));
    }

    public static int[] merge(int[] left,int[] right){
        int[] is = new int[left.length + right.length];
        for(int i=0,li=0,ri=0,ic=is.length;i<ic;i++){
            if(li>=left.length){
                is[i] = right[ri];
                ri++;
            }else if(ri >= right.length){
                is[i] = left[li];
                li++;
            }else if(left[li] < right[ri]){
                is[i] = left[li];
                li++;
            }else{
                is[i] = right[ri];
                ri++;
            }
        }
        return is;
    }

    public static void quick(int[] is){
        quick(is,0, is.length-1);
    }

    public static void quick(int[] is,int s,int e){
        if(is.length<=1){
            return;
        }
        if(s < e){
            int partition = partition(is,s,e);
            quick(is,s,partition-1);
            quick(is,partition+1,e);
        }
    }

    public static int partition(int[] is,int s,int e){
        int pivot = s,index = s+1;
        for(int i=s+1;i<=e;i++){
            if(is[i] < is[pivot]){
                swap(is,index,i);
                index++;
            }
        }
        swap(is,index-1,pivot);
        return index-1;
    }

    public static void swap(int[] is,int i,int j){
        int tmp = is[j];
        is[j] = is[i];
        is[i] = tmp;
    }

    public static void main(String[] args)throws Exception{
        int[] is = new int[]{64,12,34,73,13,83,1,46,30,10,30,102,43};
        quick(is);
        System.out.println(Arrays.toString(is));
    }
}
